package com.zhanghp.class021;

import java.util.Arrays;

/**
 * 归并排序，填函数练习风格
 * 测试链接 : https://leetcode.cn/problems/sort-an-array/
 *
 * @author zhanghp
 * @since 2024/3/5 20:24
 */
public class MergeSort {

    public static int max = 50_001;
    public static int[] help = new int[max];

    public static void main(String[] args) {
        int[] arr = {5, 1, 1, 2, 0, 0};
        int[] ints = new Solution().sortArray(arr);
        System.out.println(Arrays.toString(ints));
    }

    static class SolutionRecursion {

        public int[] sortArray(int[] nums) {
            if (nums == null || nums.length <= 1) {
                return nums;
            }
            mergeSort(nums, 0, nums.length - 1);
            return nums;
        }

        public void mergeSort(int[] arr, int l, int r) {
            if (l == r) {
                return;
            }
            int mid = l + ((r - l) >> 1);
            mergeSort(arr, l, mid);
            mergeSort(arr, mid + 1, r);
            merge(arr, l, r, mid);
        }

        public void merge(int[] arr, int l, int r, int mid) {
            int i = l, a = l;
            int b = mid + 1;
            while (a <= mid && b <= r) {
                help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
            }
            while (a <= mid) {
                help[i++] = arr[a++];
            }
            while (b <= r) {
                help[i++] = arr[b++];
            }
            for (i = l; i <= r; i++) {
                arr[i] = help[i];
            }
        }
    }

    static class Solution {
        public int[] sortArray(int[] nums) {
            if (nums == null || nums.length <= 1) {
                return nums;
            }
            mergeSort(nums);
            return nums;
        }

        /**
         * <p>
         *     用步长，从1 -> 2^n进行处理
         * </p>
         * <ul>
         *     <li>
         *         递归：从大到小
         *     </li>
         *     <li>
         *         非递归：小->大
         *     </li>
         * </ul>
         * <p>
         *   示例：[ 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1]
         *   <br/>
         *   步长：1  ->   [9|8], [7|6], [5|4], [3|2], 1  -> [8,9], [6,7], [4,5], [2,3], 1
         *   <br/>
         *   步长：2  ->   [8,9 | 6,7] , [4,5 | 2,3] , 1  -> [6,7,8,9], [2,3,4,5], 1
         *   <br/>
         *   步长：4  ->   [6,7,8,9 | 2,3,4,5] , 1        -> [2,3,4,5,6,7,8,9], 1
         *   <br/>
         *   步长：8  ->   [2,3,4,5,6,7,8,9 | 1]          -> [1,2,3,4,5,6,7,8,9]
         *   <br/>
         * </p>
         *
         * @param arr
         */
        public void mergeSort(int[] arr) {
            int n = arr.length;
            for (int l, mid, r, step = 1; step < n; step <<= 1) {
                l = 0;
                while (l < n) {
                    mid = l + step - 1;
                    if (mid + 1 >= n) {
                        break;
                    }
                    r = Math.min(n - 1, l + (step << 1) - 1);
                    merge(arr, l, mid, r);
                    l = r + 1;
                }
            }
        }

        public void merge(int[] arr, int l, int mid, int r) {
            int helpIndex = l;
            int a = l, b = mid + 1;
            while (a <= mid && b <= r) {
                help[helpIndex++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
            }
            while (a <= mid) {
                help[helpIndex++] = arr[a++];
            }
            while (b <= r) {
                help[helpIndex++] = arr[b++];
            }
            for (helpIndex = l; helpIndex <= r; helpIndex++) {
                arr[helpIndex] = help[helpIndex];

            }
        }
    }
}
